<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.0">
<meta name="google-site-verification" content="SByO7HWUKwufO-witstBrFt-yyK6q3tUlCyYwkvYPiQ" />
<meta name="baidu-site-verification" content="orhaMjPwcS" />
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic|Roboto Slab:300,300italic,400,400italic,700,700italic|Roboto Mono:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">
<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/gh/fancyapps/fancybox@3/dist/jquery.fancybox.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"lixiyan4633.gitee.io","root":"/","scheme":"Pisces","version":"7.7.2","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":true,"style":"mac"},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":true,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

  <meta name="description" content="数据结构算法打卡，参考的王铮老师在极客时间上的《数据结构与算法之美》">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构算法Day12-散列表">
<meta property="og:url" content="https://lixiyan4633.gitee.io/2020/03/26/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95Day12-%E6%95%A3%E5%88%97%E8%A1%A8/index.html">
<meta property="og:site_name" content="喜延的个人博客">
<meta property="og:description" content="数据结构算法打卡，参考的王铮老师在极客时间上的《数据结构与算法之美》">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/92/73/92c89a57e21f49d2f14f4424343a2773.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/5c/d5/5c31a3127cbc00f0c63409bbe1fbd0d5.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/91/ff/9126b0d33476777e7371b96e676e90ff.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/a4/7f/a4b77d593e4cb76acb2b0689294ec17f.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/67/43/67d12e07a7d673a9c1d14354ad029443.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/6d/cb/6d6736f986ec4b75dabc5472965fb9cb.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/ea/6e/eaefd5f4028cc7d4cfbb56b24ce8ae6e.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/17/98/17ac41d9dac454e454dcb289100bf198.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/fe/8c/fe313ed327bcf234c73ba738d975b18c.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/b5/11/b5e07bb34d532d46d127f4fcc4b78f11.jpg">
<meta property="article:published_time" content="2020-03-26T00:58:13.000Z">
<meta property="article:modified_time" content="2020-03-26T05:25:49.770Z">
<meta property="article:author" content="李喜延">
<meta property="article:tag" content="数据结构">
<meta property="article:tag" content="算法">
<meta property="article:tag" content="散列表">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://static001.geekbang.org/resource/image/92/73/92c89a57e21f49d2f14f4424343a2773.jpg">

<link rel="canonical" href="https://lixiyan4633.gitee.io/2020/03/26/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95Day12-%E6%95%A3%E5%88%97%E8%A1%A8/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true
  };
</script>

  <title>数据结构算法Day12-散列表 | 喜延的个人博客</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <div>
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">喜延的个人博客</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
        <p class="site-subtitle">我的大数据的之路</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>


<nav class="site-nav">
  
  <ul id="menu" class="menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-fw fa-home"></i>首页</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-fw fa-tags"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="fa fa-fw fa-th"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-fw fa-archive"></i>归档</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-fw fa-user"></i>关于</a>

  </li>
  </ul>

</nav>
</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content">
            

  <div class="posts-expand">
      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block " lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://lixiyan4633.gitee.io/2020/03/26/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95Day12-%E6%95%A3%E5%88%97%E8%A1%A8/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="https://tva1.sinaimg.cn/large/00831rSTly1gcyel996b4j30oa0oc1kx.jpg">
      <meta itemprop="name" content="李喜延">
      <meta itemprop="description" content="愿世界和平">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="喜延的个人博客">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          数据结构算法Day12-散列表
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>
              

              <time title="创建时间：2020-03-26 08:58:13 / 修改时间：13:25:49" itemprop="dateCreated datePublished" datetime="2020-03-26T08:58:13+08:00">2020-03-26</time>
            </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" itemprop="url" rel="index"><span itemprop="name">数据结构</span></a>
                </span>
            </span>

          
            <div class="post-description">数据结构算法打卡，参考的王铮老师在极客时间上的《数据结构与算法之美》<br> <img src="https://static001.geekbang.org/resource/image/b1/02/b1b5da27544870c9376004006387db02.jpg"></div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h1 id="1-概念"><a href="#1-概念" class="headerlink" title="1.概念"></a>1.概念</h1><p>1.通过散列函数把元素键值映射为下标，然后将数据存储在数组对应下标的位置。</p>
<p>2.按照键值查找元素的时候，可以使用同样的散列函数，将键值转化为数组下标，从对应的数组下标获取数据。</p>
<p>3.数组的一种扩展，没有数组就没有散列表。</p>
<p>举例：</p>
<p>比如参赛选手，获取他的详情，参赛选手的编号我们叫作<strong>键（key）</strong>或者<strong>关键字</strong>。我们用它来标识一个选手。我们把参赛编号转化为数组下标的映射方法就叫作<strong>散列函数</strong>（或“Hash 函数”“哈希函数”），而散列函数计算得到的值就叫作<strong>散列值</strong>（或“Hash 值”“哈希值”）。</p>
<p><img src="https://static001.geekbang.org/resource/image/92/73/92c89a57e21f49d2f14f4424343a2773.jpg" alt="img"></p>
<h1 id="2-散列函数"><a href="#2-散列函数" class="headerlink" title="2.散列函数"></a>2.散列函数</h1><h2 id="概念："><a href="#概念：" class="headerlink" title="概念："></a>概念：</h2><p>它是一个函数。我们可以把它定义成 <strong>hash(key)</strong>，其中 key 表示元素的<strong>键值</strong>，hash(key) 的值表示经过散列函数计算得到的<strong>散列值</strong>。</p>
<p>构造散列函数的三个要点：</p>
<ol>
<li><p>散列函数计算得到的散列值是一个非负整数；</p>
</li>
<li><p>如果 key1 = key2，那 hash(key1) == hash(key2)；</p>
</li>
<li><p>如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。</p>
</li>
</ol>
<p>解释：</p>
<ol>
<li>算得到的值需要从数组拿数，所以不能是负数</li>
<li>相同的key得到相同的值；</li>
<li>不同的key保证得到不同的值，因为通过算法 不同的key，通过hash计算的值可能相同，这样就会发生冲突，叫做<strong>散列冲突</strong></li>
</ol>
<h2 id="设计要点"><a href="#设计要点" class="headerlink" title="设计要点"></a>设计要点</h2><ol>
<li>散列函数不能设计的太复杂</li>
<li>散列函数生成的值，尽量随机分布</li>
</ol>
<h1 id="3-散列冲突"><a href="#3-散列冲突" class="headerlink" title="3.散列冲突"></a>3.散列冲突</h1><p>不同的key，通过hash计算的值可能相同，这样就会发生冲突，叫做<strong>散列冲突</strong></p>
<h2 id="解决办法"><a href="#解决办法" class="headerlink" title="解决办法"></a>解决办法</h2><ol>
<li>开放寻址法（open addressing）</li>
<li>链表法（chaining）</li>
</ol>
<h2 id="3-1-开放寻址法"><a href="#3-1-开放寻址法" class="headerlink" title="3.1  开放寻址法"></a>3.1  开放寻址法</h2><p>开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。</p>
<p>重新探测方法之一-<strong>线性探测（Linear Probing）</strong>。</p>
<h3 id="线性探测"><a href="#线性探测" class="headerlink" title="线性探测"></a>线性探测</h3><p><img src="https://static001.geekbang.org/resource/image/5c/d5/5c31a3127cbc00f0c63409bbe1fbd0d5.jpg" alt="img"></p>
<p>散列表的大小为 10，在元素 x 插入散列表之前，已经 6 个元素插入到散列表中。x 经过 Hash 算法之后，被散列到位置下标为 7 的位置，但是这个位置已经有数据了，所以就产生了冲突。于是我们就顺序地往后一个一个找，看有没有空闲的位置，遍历到尾部都没有找到空闲的位置，于是我们再从表头开始找，直到找到空闲位置 2，于是将其插入到这个位置。</p>
<p>查找，散列函数求出要查找元素的<strong>键值对应的散列值</strong>，然后比较数组中下标为散列值的元素和要查找的元素，如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。</p>
<p><img src="https://static001.geekbang.org/resource/image/91/ff/9126b0d33476777e7371b96e676e90ff.jpg" alt="img"></p>
<p><strong>删除</strong></p>
<p>删除需要标记元素为deleted，当遇到deleted，继续探测</p>
<p>缺点：浪费空间，可能需要遍历一整个数组，时间复杂度O(n)</p>
<p>对于开放寻址冲突解决方法，除了线性探测方法之外，还有另外两种比较经典的探测方法，<strong>二次探测（Quadratic probing）</strong>和<strong>双重散列（Double hashing）</strong>。</p>
<h3 id="二次探测"><a href="#二次探测" class="headerlink" title="二次探测"></a>二次探测</h3><p>跟线性探测很像，线性探测每次探测的步长是 1，那它探测的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0，hash(key)+12，hash(key)+22……</p>
<h3 id="双重散列"><a href="#双重散列" class="headerlink" title="双重散列"></a>双重散列</h3><p>就是不仅要使用一个散列函数。我们使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。</p>
<h2 id="装载因子"><a href="#装载因子" class="headerlink" title="装载因子"></a>装载因子</h2><p>装载因子的计算公式是：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">散列表的装载因子&#x3D;填入表中的元素个数&#x2F;散列表的长度</span><br></pre></td></tr></table></figure>

<p>一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子（load factor）来表示空位的多少,装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。</p>
<h2 id="3-2-链表法"><a href="#3-2-链表法" class="headerlink" title="3.2 链表法"></a>3.2 链表法</h2><p><strong>概念</strong></p>
<p>链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。我们来看这个图，在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。</p>
<p><img src="https://static001.geekbang.org/resource/image/a4/7f/a4b77d593e4cb76acb2b0689294ec17f.jpg" alt="img"></p>
<p>当冲突了，直接插入，删除和查找需要遍历链表时间复杂度为O(1)+O(m) ，m为链表大小。</p>
<h1 id="4-工业级的散列表"><a href="#4-工业级的散列表" class="headerlink" title="4.工业级的散列表"></a>4.工业级的散列表</h1><p>工业级的散列表需要具备以下几个基本特性：</p>
<ol>
<li>支持快速的查询，删除，插入</li>
<li>内存占用合理，不能浪费过多的空间</li>
<li>性能稳定，极端情况下，也不能退化到无法接受的状态</li>
</ol>
<p>工业级的散列表需要具备以下几个要点：</p>
<ol>
<li>设计一个合适的散列函数</li>
<li>定义装载因子阈值，并且设置动态扩容</li>
<li>选择和是散列冲突方法</li>
</ol>
<h2 id="1-装载因子过大"><a href="#1-装载因子过大" class="headerlink" title="1.装载因子过大"></a>1.装载因子过大</h2><p>随着数据的插入，装载因子会逐渐增加，当装载因子过大，需要扩容，扩容就涉及到数组搬移，因为Hash函数不变，所以原来的位置也需要改变，当删除数据，数组也需要缩容。</p>
<p><img src="https://static001.geekbang.org/resource/image/67/43/67d12e07a7d673a9c1d14354ad029443.jpg" alt="img"></p>
<h2 id="2-避免低效扩容"><a href="#2-避免低效扩容" class="headerlink" title="2.避免低效扩容"></a>2.避免低效扩容</h2><p>为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。</p>
<p>当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，我们都重复上面的过程。经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次性数据搬移，插入操作就都变得很快了。</p>
<p><img src="https://static001.geekbang.org/resource/image/6d/cb/6d6736f986ec4b75dabc5472965fb9cb.jpg" alt="img"></p>
<p>查找的时候如果找不到，就去老的散列表查找。</p>
<h2 id="3-散列冲突的方法对比"><a href="#3-散列冲突的方法对比" class="headerlink" title="3.散列冲突的方法对比"></a>3.散列冲突的方法对比</h2><blockquote>
<p>Java 中 LinkedHashMap 就采用了链表法解决冲突，ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突。</p>
</blockquote>
<ol>
<li><p>开放寻址法</p>
<p>优点：</p>
<p>​     - 可以有效地利用 CPU 缓存加快查询速度</p>
<p>​    -  序列化起来比较简单</p>
<p>缺点：</p>
<p>​    删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。</p>
</li>
</ol>
<p>​       <strong>当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。</strong></p>
<ol>
<li><p>链表法</p>
<p>优点：</p>
<p>​    - 内存的利用率比开放寻址法要高</p>
<p>​    - 对大装载因子的容忍度更高。</p>
<p>​    - 存储大对象比较友好，指针大小忽略不计</p>
<p><strong>基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。</strong></p>
</li>
</ol>
<h2 id="4-设计"><a href="#4-设计" class="headerlink" title="4.设计"></a>4.设计</h2><h3 id="4-1-初始大小"><a href="#4-1-初始大小" class="headerlink" title="4.1  初始大小"></a>4.1  初始大小</h3><p>HashMap 默认的初始大小是 16，当然这个默认值是可以设置的，如果事先知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容的次数，这样会大大提高 HashMap 的性能。</p>
<h3 id="4-2-装载因子和动态扩容"><a href="#4-2-装载因子和动态扩容" class="headerlink" title="4.2 装载因子和动态扩容"></a>4.2 装载因子和动态扩容</h3><p>最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。</p>
<h3 id="4-3-散列冲突解决方法"><a href="#4-3-散列冲突解决方法" class="headerlink" title="4.3 散列冲突解决方法"></a>4.3 散列冲突解决方法</h3><p>链表长度超过8，转为红黑树，小于8，转为链表</p>
<h3 id="4-4-散列函数"><a href="#4-4-散列函数" class="headerlink" title="4.4 散列函数"></a>4.4 散列函数</h3><p>散列函数的设计并不复杂，追求的是简单高效、分布均匀。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">hash</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> h = key.hashCode()；</span><br><span class="line">    <span class="keyword">return</span> (h ^ (h &gt;&gt;&gt; <span class="number">16</span>)) &amp; (capicity -<span class="number">1</span>); <span class="comment">//capicity表示散列表的大小</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>其中，hashCode() 返回的是 Java 对象的 hash code。比如 String 类型的对象的 hashCode() 就是下面这样：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">hashCode</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="keyword">int</span> var1 = <span class="keyword">this</span>.hash;</span><br><span class="line">  <span class="keyword">if</span>(var1 == <span class="number">0</span> &amp;&amp; <span class="keyword">this</span>.value.length &gt; <span class="number">0</span>) &#123;</span><br><span class="line">    <span class="keyword">char</span>[] var2 = <span class="keyword">this</span>.value;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> var3 = <span class="number">0</span>; var3 &lt; <span class="keyword">this</span>.value.length; ++var3) &#123;</span><br><span class="line">      var1 = <span class="number">31</span> * var1 + var2[var3];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">this</span>.hash = var1;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> var1;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h1 id="5-散列表的LRU算法"><a href="#5-散列表的LRU算法" class="headerlink" title="5.散列表的LRU算法"></a>5.散列表的LRU算法</h1><p><img src="https://static001.geekbang.org/resource/image/ea/6e/eaefd5f4028cc7d4cfbb56b24ce8ae6e.jpg" alt="img"></p>
<p>LRU中设计的到pre，next和hnext的具体含义，pre和next组成双向链表，这个链表是按照缓存的时间由大到小，组成的一个缓存队列；对于hnext作用是，在最新时间插入缓存数据时，通过哈希函数得出的冲突，用其连接。<br>总结：在双向链表中，时间是从大到小；在hnext组成的拉链中，时间从左到右依次变小。<br>核心：数据结构的设计，一定是建立应用场景之上，根据最新时间加入缓存。</p>
<p><strong>如何查找一个数据？</strong></p>
<p>散列表中查找数据的时间复杂度接近 O(1)，所以通过散列表，我们可以很快地在缓存中找到一个数据。当找到数据之后，我们还需要将它移动到双向链表的尾部。</p>
<p><strong>如何删除一个数据？</strong></p>
<p>我们需要找到数据所在的结点，然后将结点删除。借助散列表，我们可以在 O(1) 时间复杂度里找到要删除的结点。因为我们的链表是双向链表，双向链表可以通过前驱指针 O(1) 时间复杂度获取前驱结点，所以在双向链表中，删除结点只需要 O(1) 的时间复杂度。</p>
<p><strong>如何添加一个数据？</strong></p>
<p>添加数据到缓存稍微有点麻烦，我们需要先看这个数据是否已经在缓存中。如果已经在其中，需要将其移动到双向链表的尾部；如果不在其中，还要看缓存有没有满。如果满了，则将双向链表头部的结点删除，然后再将数据放到链表的尾部；如果没有满，就直接将数据放到链表的尾部。</p>
<h1 id="6-Java-LinkedHashMap"><a href="#6-Java-LinkedHashMap" class="headerlink" title="6.Java LinkedHashMap"></a>6.Java LinkedHashMap</h1><p>Linked -&gt; 双向链表</p>
<p>1.顺序输出</p>
<p>2.按照访问顺序来遍历数据</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 10是初始大小，0.75是装载因子，true是表示按照访问时间排序</span></span><br><span class="line">HashMap&lt;Integer, Integer&gt; m = <span class="keyword">new</span> LinkedHashMap&lt;&gt;(<span class="number">10</span>, <span class="number">0.75f</span>, <span class="keyword">true</span>);</span><br><span class="line">m.put(<span class="number">3</span>, <span class="number">11</span>);</span><br><span class="line">m.put(<span class="number">1</span>, <span class="number">12</span>);</span><br><span class="line">m.put(<span class="number">5</span>, <span class="number">23</span>);</span><br><span class="line">m.put(<span class="number">2</span>, <span class="number">22</span>);</span><br><span class="line"></span><br><span class="line">m.put(<span class="number">3</span>, <span class="number">26</span>);</span><br><span class="line">m.get(<span class="number">5</span>);</span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span> (Map.Entry e : m.entrySet()) &#123;</span><br><span class="line">  System.out.println(e.getKey());</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>解析：</p>
<p>每次调用 put() 函数，往 LinkedHashMap 中添加数据的时候，都会将数据添加到链表的尾部，所以，在前四个操作完成之后，链表中的数据是下面这样：</p>
<p><img src="https://static001.geekbang.org/resource/image/17/98/17ac41d9dac454e454dcb289100bf198.jpg" alt="img"></p>
<p><code>m.put(3, 26);</code></p>
<p><img src="https://static001.geekbang.org/resource/image/fe/8c/fe313ed327bcf234c73ba738d975b18c.jpg" alt="img"></p>
<p><code>m.get(5);</code></p>
<p><img src="https://static001.geekbang.org/resource/image/b5/11/b5e07bb34d532d46d127f4fcc4b78f11.jpg" alt="img"></p>
<p>所以输出是1，2，3，5</p>
<h1 id="问题："><a href="#问题：" class="headerlink" title="问题："></a>问题：</h1><p><strong>1.Word 文档中单词拼写检查功能是如何实现的？</strong></p>
<p>英文单词大概20万，每个大约10个字节，总计2M大小，扩大10倍，也就20M，可以放到内存中，存在散列表中，用户输入单词，就去散列表查询，查不到就提示单词书写错误。</p>
<p><strong>2.假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？</strong></p>
<p>遍历 10 万条数据，以 URL 为 key，访问次数为 value，存入散列表，同时记录下访问次数的最大值 K，时间复杂度 O(N)。</p>
<p>如果 K 不是很大，可以使用桶排序，时间复杂度 O(N)。如果 K 非常大（比如大于 10 万），就使用快速排序，复杂度 O(NlogN)。</p>
<p><strong>3.有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串？</strong></p>
<p>以第一个字符串数组构建散列表，key 为字符串，value 为出现次数。再遍历第二个字符串数组，以字符串为 key 在散列表中查找，如果 value 大于零，说明存在相同字符串。时间复杂度 O(N)。</p>
<p><strong>4.假设猎聘网有 10 万名猎头，每个猎头都可以通过做任务（比如发布职位）来积累积分，然后通过积分来下载简历。假设你是猎聘网的一名工程师，如何在内存中存储这 10 万个猎头 ID 和积分信息，让它能够支持这样几个操作：</strong></p>
<ul>
<li>根据猎头的 ID 快速查找、删除、更新这个猎头的积分信息；</li>
<li>查找积分在某个区间的猎头 ID 列表；</li>
</ul>
<p>1）ID 在散列表中所以可以 O(1) 查找到这个猎头；<br>2）积分以跳表存储，跳表支持区间查询；</p>

    </div>

    
    
    

      <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag"><i class="fa fa-tag"></i> 数据结构</a>
              <a href="/tags/%E7%AE%97%E6%B3%95/" rel="tag"><i class="fa fa-tag"></i> 算法</a>
              <a href="/tags/%E6%95%A3%E5%88%97%E8%A1%A8/" rel="tag"><i class="fa fa-tag"></i> 散列表</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/2020/03/25/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95Day11-%E8%B7%B3%E8%A1%A8/" rel="prev" title="数据结构算法Day11-跳表">
      <i class="fa fa-chevron-left"></i> 数据结构算法Day11-跳表
    </a></div>
      <div class="post-nav-item">
    <a href="/2020/03/27/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95Day13-%E4%BA%8C%E5%8F%89%E6%A0%91/" rel="next" title="数据结构算法Day13-二叉树">
      数据结构算法Day13-二叉树 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  
<div>
    
    <div>
    
        <div style="text-align:center;color: #ccc;font-size:14px;">-------------　　　　本文结束　<i class="fa fa-heart"></i>　感谢您的阅读　　　　-------------</div>
    
</div>


    
 </div>

  </div>


          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#1-概念"><span class="nav-number">1.</span> <span class="nav-text">1.概念</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#2-散列函数"><span class="nav-number">2.</span> <span class="nav-text">2.散列函数</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#概念："><span class="nav-number">2.1.</span> <span class="nav-text">概念：</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#设计要点"><span class="nav-number">2.2.</span> <span class="nav-text">设计要点</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#3-散列冲突"><span class="nav-number">3.</span> <span class="nav-text">3.散列冲突</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#解决办法"><span class="nav-number">3.1.</span> <span class="nav-text">解决办法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-1-开放寻址法"><span class="nav-number">3.2.</span> <span class="nav-text">3.1  开放寻址法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#线性探测"><span class="nav-number">3.2.1.</span> <span class="nav-text">线性探测</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#二次探测"><span class="nav-number">3.2.2.</span> <span class="nav-text">二次探测</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#双重散列"><span class="nav-number">3.2.3.</span> <span class="nav-text">双重散列</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#装载因子"><span class="nav-number">3.3.</span> <span class="nav-text">装载因子</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-2-链表法"><span class="nav-number">3.4.</span> <span class="nav-text">3.2 链表法</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#4-工业级的散列表"><span class="nav-number">4.</span> <span class="nav-text">4.工业级的散列表</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#1-装载因子过大"><span class="nav-number">4.1.</span> <span class="nav-text">1.装载因子过大</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#2-避免低效扩容"><span class="nav-number">4.2.</span> <span class="nav-text">2.避免低效扩容</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-散列冲突的方法对比"><span class="nav-number">4.3.</span> <span class="nav-text">3.散列冲突的方法对比</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#4-设计"><span class="nav-number">4.4.</span> <span class="nav-text">4.设计</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#4-1-初始大小"><span class="nav-number">4.4.1.</span> <span class="nav-text">4.1  初始大小</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#4-2-装载因子和动态扩容"><span class="nav-number">4.4.2.</span> <span class="nav-text">4.2 装载因子和动态扩容</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#4-3-散列冲突解决方法"><span class="nav-number">4.4.3.</span> <span class="nav-text">4.3 散列冲突解决方法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#4-4-散列函数"><span class="nav-number">4.4.4.</span> <span class="nav-text">4.4 散列函数</span></a></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#5-散列表的LRU算法"><span class="nav-number">5.</span> <span class="nav-text">5.散列表的LRU算法</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#6-Java-LinkedHashMap"><span class="nav-number">6.</span> <span class="nav-text">6.Java LinkedHashMap</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#问题："><span class="nav-number">7.</span> <span class="nav-text">问题：</span></a></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="李喜延"
      src="https://tva1.sinaimg.cn/large/00831rSTly1gcyel996b4j30oa0oc1kx.jpg">
  <p class="site-author-name" itemprop="name">李喜延</p>
  <div class="site-description" itemprop="description">愿世界和平</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">25</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">4</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">25</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">李喜延</span>
</div>

        








      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/jquery@3/dist/jquery.min.js"></script>
  <script src="//cdn.jsdelivr.net/gh/fancyapps/fancybox@3/dist/jquery.fancybox.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/pisces.js"></script>


<script src="/js/next-boot.js"></script>




  















  

  

</body>
</html>
